from typing import List


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        intervals.sort(key=lambda x: x[0])

        res = [intervals[0]]
        j = 0
        for temp in intervals[1:]:
            if res[j][-1] < temp[0]:
                res.append(temp)
                j += 1
            elif temp[0] <= res[j][-1] <= temp[-1]:
                res[j] = [res[j][0], temp[-1]]

        return res


#leetcode 56
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
s = Solution()
print(s.merge(intervals))
